package com.gxc.mydouble;

/**
 * 50. Pow(x, n)
 实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。
 */
public class MyPow {

    public static void main(String[] args) {
        //System.out.println(handle(2, 10));
        //System.out.println(handle(2.1, 3));
        System.out.println(handle(2, -2));
    }

    public static double handle(double x, int n) {
        double res = 1;
        boolean positive = n>0 ?true:false;
        for (int i = 0; i < Math.abs(n); i++) {
            res = res * x;
        }
        return positive?res:1/res;
    }

    /**
     * 递归
     * 快速幂
     * @param x
     * @param n
     * @return
     */
    public static double handle2(double x, int n) {
        double res = 1;
        boolean positive = n>0 ?true:false;
        res = quickMul(x, Math.abs(n));
        return positive?res:1/res;
    }

    private static double quickMul(double x, int n) {
        if (n == 0) return 1;
        double v = quickMul(x * x, n / 2);
        return n % 2 == 0?v:v * x;
    }

    /**
     * 快速幂 + 迭代
     * @param x
     * @param n
     * @return
     */
    public static double handle3(double x, int n) {
        double res = 1;
        boolean positive = n>0 ?true:false;
        int m = Math.abs(n);
        double x_contribute = x;
        while (m > 0) {
            if (m % 2 == 1) {
                // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                res *= x_contribute;
            }
            // 将贡献不断地平方
            x_contribute *= x_contribute;
            // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
            m /= 2;
        }
        return positive?res:1/res;
    }
}
